#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

//Assume we have 2^30 bytes empty area.
#define MAX_SIZE 30

struct tree
{
    int max_block;
    tree *lc, *rc;
    tree()
    {
        lc = NULL;
        rc = NULL;
    }
}*root;

int my_allocate(tree *r, int root_size, int need_size)
{
    if (r->max_block < need_size)
        return -1;
    if (root_size == need_size)
    {
        r->max_block = -1;
        return 0;
    }
    if (r->lc == NULL)
    {
        r->lc = new tree();
        r->rc = new tree();
        r->lc->max_block = r->rc->max_block = root_size - 1;
    }
    
    int ret;
    if (r->lc->max_block >= need_size)
        ret = my_allocate(r->lc, root_size - 1, need_size);
    else
        ret = my_allocate(r->rc, root_size - 1, need_size) | (1 << (root_size - 1));
    r->max_block = max(r->lc->max_block, r->rc->max_block);
    return ret;
}

bool my_free(tree *r, int root_size, int start_pos, int now_pos)
{
    if (r->max_block == -1)
        if (now_pos != start_pos)
            return false;
        else
        {
            r->max_block = root_size;
            return true;
        }
    if (r->lc == NULL)
        return false;
    int mid = now_pos | (1 << (root_size - 1));
    if (start_pos < mid)
    {
        if (!my_free(r->lc, root_size - 1, start_pos, now_pos))
            return false;
    }
    else
    {
        if (!my_free(r->rc, root_size - 1, start_pos, now_pos + mid))
            return false;
    }
    if (r->lc->max_block == root_size - 1 && r->rc->max_block == root_size - 1)
        r->max_block = root_size;
    else
        r->max_block = max(r->lc->max_block, r->rc->max_block);
    return true;
}

int main()
{
    // initialization.
    root = new tree();
    root->max_block = MAX_SIZE;
    
    while(1)
    {
        int opt;
        printf("Please enter the operation: 1. allocate 2. free\n");
        scanf("%d",&opt);
        if (opt == 1)
        {
            printf("Please enter the size you want: ");
            scanf("%d", &opt);
            int sz = 1;
            for (; (1<<sz) < opt; ++sz);
            if (sz > root->max_block)
                printf("Allocate failed.\n");
            else
            {
                int ans = my_allocate(root, MAX_SIZE, sz);
                printf("Addresses from %d to %d is allocated.\n", ans, ans + (1<<sz));
            }
        }
        else
        {
            printf("Please enter the starting address of the block you want to free: ");
            scanf("%d", &opt);
            if (my_free(root, MAX_SIZE, opt, 0))
                printf("Free succeed.\n");
            else
                printf("Free failed.\n");
        }
    }
}
